package com.example.demo.leetcode.top100;

import java.util.*;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _80划分字母区间
 * @description
 * @date 2023/06/28 17:12
 * <p>
 * ******************************************************
 */
public class _80划分字母区间 {

    public List<Integer> partitionLabels(String s) {
        int length = s.length();
        String[] strings = s.split("");

        Map<String, List<Integer>> indexMap = new HashMap<>();
        for (int i = 0; i < length; i++) {
            int index = s.indexOf(strings[i]);
            int lastIndex = s.lastIndexOf(strings[i]);
            if (!indexMap.containsKey(strings[i])) {
                indexMap.put(strings[i], Arrays.asList(index, lastIndex));
            }
        }

        int[][] intervals = new int[indexMap.size()][2];
        int i = 0;
        for (List<Integer> value : indexMap.values()) {
            intervals[i][0] = value.get(0);
            intervals[i++][1] = value.get(1);
        }

        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });

        LinkedList<LinkedList<Integer>> res = new LinkedList<>();
        LinkedList<Integer> first = new LinkedList<Integer>(){{
            add(intervals[0][0]);
            add(intervals[0][1]);
        }};
        res.add(first);

        for (int j = 1; j < intervals.length; j++) {
            int[] curr = intervals[j];
            LinkedList<Integer> last = res.getLast();

            if (last.getLast() >= curr[0]) {
                if (last.getLast() < curr[1]) {
                    last.removeLast();
                    last.add(curr[1]);
                }
            } else {
                LinkedList<Integer> list = new LinkedList<Integer>(){{
                    add(curr[0]);
                    add(curr[1]);
                }};
                res.add(list);
            }

        }

        List<Integer> result = new LinkedList<>();
        for (int j = 0; j < res.size(); j++) {
            result.add(res.get(j).getLast() - res.get(j).getFirst() + 1);
        }
        return result;
    }
}
